package com.example.arithmeticleetcode.learnArithmetic2.sort;

/**
 * @program: arithmetic-leetcode
 * @description: 插入排序 最好的时间复杂度 O(n) 最坏 平均复杂度O(n^2)  空间复杂度 O(1)  稳定排序
 * @author: FangZhen
 * @create: 2020-11-05 17:09
 **/
public class InsertionSort<E extends Comparable<E>> extends Sort<E> {

    @Override
    protected void sort() {
        for (int begin = 1, len = array.length; begin < len; begin++) {
            int tempBegin = begin;
            while (tempBegin > 0 && cmp(tempBegin, tempBegin - 1) < 0) {
                swap(tempBegin, tempBegin - 1);
                tempBegin--;
            }
        }
    }
}
